#include <iostream>
#include <vector>
#include <BinaryTree.hpp>
#include <Vector.hpp>
#include <deque>

using namespace std;

class Solution
{
public:
    vector<double> averageOfLevels(TreeNode *root)
    {
        vector<double> sum;
        vector<int> count;
        if (root == nullptr)
            return vector<double>{};
        dfs(root, 0, sum, count);
        for (int i = 0; i < sum.size(); i++)
        {
            sum[i] = sum[i] / count[i];
        }
        return sum;
    }

    void
    dfs(TreeNode *node, int level, vector<double> &sum, vector<int> &count)
    {
        if (sum.size() < level + 1)
        {
            sum.push_back(node->val);
            count.push_back(1);
        }
        else
        {
            sum[level] += node->val;
            count[level]++;
        }
        if (node->left)
        {
            dfs(node->left, level + 1, sum, count);
        }
        if (node->right)
        {
            dfs(node->right, level + 1, sum, count);
        }
    }
};
int main()
{
    cout << "Code637" << endl;
    Solution s;
    TreeNode *root = CreatTree("[3,9,20,null,null,15,7]", "null");
    auto res = s.averageOfLevels(root);
    PrintVector(res);
    return 0;
}